JZ21 栈的压入、弹出序列

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106

这题我个人觉得应该算难，因为思路不太好想，这种题就是

方法一：

这个写的有点复杂了，具体看方法二会好点

import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        boolean result = false;
        int flag = popA.length - 1;
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < pushA.length; i++) {
            list.add(pushA[i]);
            if (pushA[i] == popA[flag]) {
                for(int j = list.size() - 1;j > 0;j--) {
                    if (list.get(j) != popA[flag]) {
                        return false;
                    }
                    flag--;
                }
                list.clear();
            }
        }
        
        return list.isEmpty();
    }
}

方法二：

思路：新建一个栈，将数组 A 压入栈中，当栈顶元素等于数组 B 时，就将其出栈，当循环结束时，判断栈是否为空，若为空则返回 true

import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if (pushA == null || popA == null || pushA.length != popA.length) return false;
        if (pushA.length == 0) return popA.length == 0;

        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0;i < pushA.length; i++) {
            stack.push(pushA[i]);
            // 只有一样时才弹出元素
            while (!stack.isEmpty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        
        return stack.isEmpty();
    }
}